package leetcode.median;

/**
 * ClassName: $96_NumTrees
 * Description:
 * date: 2021-11-17 22:16
 *
 * @author liyifan
 */
public class $96_NumTrees {

    int[][] dp;

    public int numTrees2(int n){
        dp = new int[n + 1][n + 1];
        return count(1, n);
    }

    int count(int low, int high) {
        if (low > high)
            return 1;
        if (dp[low][high] != 0)
            return dp[low][high];
        int res = 0;
        for (int i = low; i <= high; i++) {
            int left = count(low, i - 1);
            int right = count(i + 1, high);
            res += left * right;
        }
        dp[low][high] = res;
        return res;
    }


    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2;i <= n;i++) {
            for (int j = 1;j <= i;j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}
